class Solution {
public:
    bool row[9][10];
    bool col[9][10];
    bool grid[3][3][10];
    bool check[9][9];
    void solveSudoku(vector<vector<char>>& board) 
    {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]!='.')
                {
                    int num=board[i][j]-'0';
                    row[i][num]=col[j][num]=grid[i/3][j/3][num]=check[i][j]=true;
                }
            }
        }
        dfs(0,0,board);
    }
    bool dfs(int i,int j,vector<vector<char>>& board)
    {
        if(j>=9)
        {
            j=0;
            i++;
        }
        if(i>=9) 
        {
            return true;
        }
        if(!check[i][j])
        {
            for(char num='1';num<='9';num++)
            {
                int nums=num-'0';
                if(!row[i][nums]&&!col[j][nums]&&!grid[i/3][j/3][nums])
                {
                    board[i][j]=num;
                    check[i][j]=true;
                     row[i][nums]=col[j][nums]=grid[i/3][j/3][nums]=check[i][j]=true;
                     if(dfs(i,j+1,board)) return true;
                     board[i][j]='.';
                    check[i][j]=false;
                    row[i][nums]=col[j][nums]=grid[i/3][j/3][nums]=check[i][j]=false;
                }
            }
            return false;
        }
        else
        {
            return dfs(i,j+1,board);
        }
    }
};